/*
 * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 * (C) Copyright IBM Corp. 1998-2003, All Rights Reserved
 *
 */

package java.awt.font;

import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics2D;
import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.GeneralPath;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.awt.im.InputMethodHighlight;
import java.awt.image.BufferedImage;
import java.text.Annotation;
import java.text.AttributedCharacterIterator;
import java.text.AttributedCharacterIterator.Attribute;
import java.text.Bidi;
import java.text.CharacterIterator;
import java.util.Hashtable;
import java.util.Map;
import sun.font.AttributeValues;
import sun.font.BidiUtils;
import sun.font.CoreMetrics;
import sun.font.Decoration;
import sun.font.FontLineMetrics;
import sun.font.FontResolver;
import sun.font.GraphicComponent;
import sun.font.LayoutPathImpl;
import sun.font.LayoutPathImpl.EmptyPath;
import sun.font.LayoutPathImpl.SegmentPathBuilder;
import sun.font.TextLabelFactory;
import sun.font.TextLineComponent;
import sun.text.CodePointIterator;

import java.awt.geom.Line2D;

final class TextLine {

  static final class TextLineMetrics {

    public final float ascent;
    public final float descent;
    public final float leading;
    public final float advance;

    public TextLineMetrics(float ascent,
        float descent,
        float leading,
        float advance) {
      this.ascent = ascent;
      this.descent = descent;
      this.leading = leading;
      this.advance = advance;
    }
  }

  private TextLineComponent[] fComponents;
  private float[] fBaselineOffsets;
  private int[] fComponentVisualOrder; // if null, ltr
  private float[] locs; // x,y pairs for components in visual order
  private char[] fChars;
  private int fCharsStart;
  private int fCharsLimit;
  private int[] fCharVisualOrder;  // if null, ltr
  private int[] fCharLogicalOrder; // if null, ltr
  private byte[] fCharLevels;     // if null, 0
  private boolean fIsDirectionLTR;
  private LayoutPathImpl lp;
  private boolean isSimple;
  private Rectangle pixelBounds;
  private FontRenderContext frc;

  private TextLineMetrics fMetrics = null; // built on demand in getMetrics

  public TextLine(FontRenderContext frc,
      TextLineComponent[] components,
      float[] baselineOffsets,
      char[] chars,
      int charsStart,
      int charsLimit,
      int[] charLogicalOrder,
      byte[] charLevels,
      boolean isDirectionLTR) {

    int[] componentVisualOrder = computeComponentOrder(components,
        charLogicalOrder);

    this.frc = frc;
    fComponents = components;
    fBaselineOffsets = baselineOffsets;
    fComponentVisualOrder = componentVisualOrder;
    fChars = chars;
    fCharsStart = charsStart;
    fCharsLimit = charsLimit;
    fCharLogicalOrder = charLogicalOrder;
    fCharLevels = charLevels;
    fIsDirectionLTR = isDirectionLTR;
    checkCtorArgs();

    init();
  }

  private void checkCtorArgs() {

    int checkCharCount = 0;
    for (int i = 0; i < fComponents.length; i++) {
      checkCharCount += fComponents[i].getNumCharacters();
    }

    if (checkCharCount != this.characterCount()) {
      throw new IllegalArgumentException("Invalid TextLine!  " +
          "char count is different from " +
          "sum of char counts of components.");
    }
  }

  private void init() {

    // first, we need to check for graphic components on the TOP or BOTTOM baselines.  So
    // we perform the work that used to be in getMetrics here.

    float ascent = 0;
    float descent = 0;
    float leading = 0;
    float advance = 0;

    // ascent + descent must not be less than this value
    float maxGraphicHeight = 0;
    float maxGraphicHeightWithLeading = 0;

    // walk through EGA's
    TextLineComponent tlc;
    boolean fitTopAndBottomGraphics = false;

    isSimple = true;

    for (int i = 0; i < fComponents.length; i++) {
      tlc = fComponents[i];

      isSimple &= tlc.isSimple();

      CoreMetrics cm = tlc.getCoreMetrics();

      byte baseline = (byte) cm.baselineIndex;

      if (baseline >= 0) {
        float baselineOffset = fBaselineOffsets[baseline];

        ascent = Math.max(ascent, -baselineOffset + cm.ascent);

        float gd = baselineOffset + cm.descent;
        descent = Math.max(descent, gd);

        leading = Math.max(leading, gd + cm.leading);
      } else {
        fitTopAndBottomGraphics = true;
        float graphicHeight = cm.ascent + cm.descent;
        float graphicHeightWithLeading = graphicHeight + cm.leading;
        maxGraphicHeight = Math.max(maxGraphicHeight, graphicHeight);
        maxGraphicHeightWithLeading = Math.max(maxGraphicHeightWithLeading,
            graphicHeightWithLeading);
      }
    }

    if (fitTopAndBottomGraphics) {
      if (maxGraphicHeight > ascent + descent) {
        descent = maxGraphicHeight - ascent;
      }
      if (maxGraphicHeightWithLeading > ascent + leading) {
        leading = maxGraphicHeightWithLeading - ascent;
      }
    }

    leading -= descent;

    // we now know enough to compute the locs, but we need the final loc
    // for the advance before we can create the metrics object

    if (fitTopAndBottomGraphics) {
      // we have top or bottom baselines, so expand the baselines array
      // full offsets are needed by CoreMetrics.effectiveBaselineOffset
      fBaselineOffsets = new float[]{
          fBaselineOffsets[0],
          fBaselineOffsets[1],
          fBaselineOffsets[2],
          descent,
          -ascent
      };
    }

    float x = 0;
    float y = 0;
    CoreMetrics pcm = null;

    boolean needPath = false;
    locs = new float[fComponents.length * 2 + 2];

    for (int i = 0, n = 0; i < fComponents.length; ++i, n += 2) {
      tlc = fComponents[getComponentLogicalIndex(i)];
      CoreMetrics cm = tlc.getCoreMetrics();

      if ((pcm != null) &&
          (pcm.italicAngle != 0 || cm.italicAngle != 0) &&  // adjust because of italics
          (pcm.italicAngle != cm.italicAngle ||
              pcm.baselineIndex != cm.baselineIndex ||
              pcm.ssOffset != cm.ssOffset)) {

        // 1) compute the area of overlap - min effective ascent and min effective descent
        // 2) compute the x positions along italic angle of ascent and descent for left and right
        // 3) compute maximum left - right, adjust right position by this value
        // this is a crude form of kerning between textcomponents

        // note glyphvectors preposition glyphs based on offset,
        // so tl doesn't need to adjust glyphvector position
        // 1)
        float pb = pcm.effectiveBaselineOffset(fBaselineOffsets);
        float pa = pb - pcm.ascent;
        float pd = pb + pcm.descent;
        // pb += pcm.ssOffset;

        float cb = cm.effectiveBaselineOffset(fBaselineOffsets);
        float ca = cb - cm.ascent;
        float cd = cb + cm.descent;
        // cb += cm.ssOffset;

        float a = Math.max(pa, ca);
        float d = Math.min(pd, cd);

        // 2)
        float pax = pcm.italicAngle * (pb - a);
        float pdx = pcm.italicAngle * (pb - d);

        float cax = cm.italicAngle * (cb - a);
        float cdx = cm.italicAngle * (cb - d);

        // 3)
        float dax = pax - cax;
        float ddx = pdx - cdx;
        float dx = Math.max(dax, ddx);

        x += dx;
        y = cb;
      } else {
        // no italic adjustment for x, but still need to compute y
        y = cm.effectiveBaselineOffset(fBaselineOffsets); // + cm.ssOffset;
      }

      locs[n] = x;
      locs[n + 1] = y;

      x += tlc.getAdvance();
      pcm = cm;

      needPath |= tlc.getBaselineTransform() != null;
    }

    // do we want italic padding at the right of the line?
    if (pcm.italicAngle != 0) {
      float pb = pcm.effectiveBaselineOffset(fBaselineOffsets);
      float pa = pb - pcm.ascent;
      float pd = pb + pcm.descent;
      pb += pcm.ssOffset;

      float d;
      if (pcm.italicAngle > 0) {
        d = pb + pcm.ascent;
      } else {
        d = pb - pcm.descent;
      }
      d *= pcm.italicAngle;

      x += d;
    }
    locs[locs.length - 2] = x;
    // locs[locs.length - 1] = 0; // final offset is always back on baseline

    // ok, build fMetrics since we have the final advance
    advance = x;
    fMetrics = new TextLineMetrics(ascent, descent, leading, advance);

    // build path if we need it
    if (needPath) {
      isSimple = false;

      Point2D.Double pt = new Point2D.Double();
      double tx = 0, ty = 0;
      SegmentPathBuilder builder = new SegmentPathBuilder();
      builder.moveTo(locs[0], 0);
      for (int i = 0, n = 0; i < fComponents.length; ++i, n += 2) {
        tlc = fComponents[getComponentLogicalIndex(i)];
        AffineTransform at = tlc.getBaselineTransform();
        if (at != null &&
            ((at.getType() & AffineTransform.TYPE_TRANSLATION) != 0)) {
          double dx = at.getTranslateX();
          double dy = at.getTranslateY();
          builder.moveTo(tx += dx, ty += dy);
        }
        pt.x = locs[n + 2] - locs[n];
        pt.y = 0;
        if (at != null) {
          at.deltaTransform(pt, pt);
        }
        builder.lineTo(tx += pt.x, ty += pt.y);
      }
      lp = builder.complete();

      if (lp == null) { // empty path
        tlc = fComponents[getComponentLogicalIndex(0)];
        AffineTransform at = tlc.getBaselineTransform();
        if (at != null) {
          lp = new EmptyPath(at);
        }
      }
    }
  }

  public Rectangle getPixelBounds(FontRenderContext frc, float x, float y) {
    Rectangle result = null;

    // if we have a matching frc, set it to null so we don't have to test it
    // for each component
    if (frc != null && frc.equals(this.frc)) {
      frc = null;
    }

    // only cache integral locations with the default frc, this is a bit strict
    int ix = (int) Math.floor(x);
    int iy = (int) Math.floor(y);
    float rx = x - ix;
    float ry = y - iy;
    boolean canCache = frc == null && rx == 0 && ry == 0;

    if (canCache && pixelBounds != null) {
      result = new Rectangle(pixelBounds);
      result.x += ix;
      result.y += iy;
      return result;
    }

    // couldn't use cache, or didn't have it, so compute

    if (isSimple) { // all glyphvectors with no decorations, no layout path
      for (int i = 0, n = 0; i < fComponents.length; i++, n += 2) {
        TextLineComponent tlc = fComponents[getComponentLogicalIndex(i)];
        Rectangle pb = tlc.getPixelBounds(frc, locs[n] + rx, locs[n + 1] + ry);
        if (!pb.isEmpty()) {
          if (result == null) {
            result = pb;
          } else {
            result.add(pb);
          }
        }
      }
      if (result == null) {
        result = new Rectangle(0, 0, 0, 0);
      }
    } else { // draw and test
      final int MARGIN = 3;
      Rectangle2D r2d = getVisualBounds();
      if (lp != null) {
        r2d = lp.mapShape(r2d).getBounds();
      }
      Rectangle bounds = r2d.getBounds();
      BufferedImage im = new BufferedImage(bounds.width + MARGIN * 2,
          bounds.height + MARGIN * 2,
          BufferedImage.TYPE_INT_ARGB);

      Graphics2D g2d = im.createGraphics();
      g2d.setColor(Color.WHITE);
      g2d.fillRect(0, 0, im.getWidth(), im.getHeight());

      g2d.setColor(Color.BLACK);
      draw(g2d, rx + MARGIN - bounds.x, ry + MARGIN - bounds.y);

      result = computePixelBounds(im);
      result.x -= MARGIN - bounds.x;
      result.y -= MARGIN - bounds.y;
    }

    if (canCache) {
      pixelBounds = new Rectangle(result);
    }

    result.x += ix;
    result.y += iy;
    return result;
  }

  static Rectangle computePixelBounds(BufferedImage im) {
    int w = im.getWidth();
    int h = im.getHeight();

    int l = -1, t = -1, r = w, b = h;

    {
      // get top
      int[] buf = new int[w];
      loop:
      while (++t < h) {
        im.getRGB(0, t, buf.length, 1, buf, 0, w); // w ignored
        for (int i = 0; i < buf.length; i++) {
          if (buf[i] != -1) {
            break loop;
          }
        }
      }
    }

    // get bottom
    {
      int[] buf = new int[w];
      loop:
      while (--b > t) {
        im.getRGB(0, b, buf.length, 1, buf, 0, w); // w ignored
        for (int i = 0; i < buf.length; ++i) {
          if (buf[i] != -1) {
            break loop;
          }
        }
      }
      ++b;
    }

    // get left
    {
      loop:
      while (++l < r) {
        for (int i = t; i < b; ++i) {
          int v = im.getRGB(l, i);
          if (v != -1) {
            break loop;
          }
        }
      }
    }

    // get right
    {
      loop:
      while (--r > l) {
        for (int i = t; i < b; ++i) {
          int v = im.getRGB(r, i);
          if (v != -1) {
            break loop;
          }
        }
      }
      ++r;
    }

    return new Rectangle(l, t, r - l, b - t);
  }

  private abstract static class Function {

    abstract float computeFunction(TextLine line,
        int componentIndex,
        int indexInArray);
  }

  private static Function fgPosAdvF = new Function() {
    float computeFunction(TextLine line,
        int componentIndex,
        int indexInArray) {

      TextLineComponent tlc = line.fComponents[componentIndex];
      int vi = line.getComponentVisualIndex(componentIndex);
      return line.locs[vi * 2] + tlc.getCharX(indexInArray) + tlc.getCharAdvance(indexInArray);
    }
  };

  private static Function fgAdvanceF = new Function() {

    float computeFunction(TextLine line,
        int componentIndex,
        int indexInArray) {

      TextLineComponent tlc = line.fComponents[componentIndex];
      return tlc.getCharAdvance(indexInArray);
    }
  };

  private static Function fgXPositionF = new Function() {

    float computeFunction(TextLine line,
        int componentIndex,
        int indexInArray) {

      int vi = line.getComponentVisualIndex(componentIndex);
      TextLineComponent tlc = line.fComponents[componentIndex];
      return line.locs[vi * 2] + tlc.getCharX(indexInArray);
    }
  };

  private static Function fgYPositionF = new Function() {

    float computeFunction(TextLine line,
        int componentIndex,
        int indexInArray) {

      TextLineComponent tlc = line.fComponents[componentIndex];
      float charPos = tlc.getCharY(indexInArray);

      // charPos is relative to the component - adjust for
      // baseline

      return charPos + line.getComponentShift(componentIndex);
    }
  };

  public int characterCount() {

    return fCharsLimit - fCharsStart;
  }

  public boolean isDirectionLTR() {

    return fIsDirectionLTR;
  }

  public TextLineMetrics getMetrics() {
    return fMetrics;
  }

  public int visualToLogical(int visualIndex) {

    if (fCharLogicalOrder == null) {
      return visualIndex;
    }

    if (fCharVisualOrder == null) {
      fCharVisualOrder = BidiUtils.createInverseMap(fCharLogicalOrder);
    }

    return fCharVisualOrder[visualIndex];
  }

  public int logicalToVisual(int logicalIndex) {

    return (fCharLogicalOrder == null) ?
        logicalIndex : fCharLogicalOrder[logicalIndex];
  }

  public byte getCharLevel(int logicalIndex) {

    return fCharLevels == null ? 0 : fCharLevels[logicalIndex];
  }

  public boolean isCharLTR(int logicalIndex) {

    return (getCharLevel(logicalIndex) & 0x1) == 0;
  }

  public int getCharType(int logicalIndex) {

    return Character.getType(fChars[logicalIndex + fCharsStart]);
  }

  public boolean isCharSpace(int logicalIndex) {

    return Character.isSpaceChar(fChars[logicalIndex + fCharsStart]);
  }

  public boolean isCharWhitespace(int logicalIndex) {

    return Character.isWhitespace(fChars[logicalIndex + fCharsStart]);
  }

  public float getCharAngle(int logicalIndex) {

    return getCoreMetricsAt(logicalIndex).italicAngle;
  }

  public CoreMetrics getCoreMetricsAt(int logicalIndex) {

    if (logicalIndex < 0) {
      throw new IllegalArgumentException("Negative logicalIndex.");
    }

    if (logicalIndex > fCharsLimit - fCharsStart) {
      throw new IllegalArgumentException("logicalIndex too large.");
    }

    int currentTlc = 0;
    int tlcStart = 0;
    int tlcLimit = 0;

    do {
      tlcLimit += fComponents[currentTlc].getNumCharacters();
      if (tlcLimit > logicalIndex) {
        break;
      }
      ++currentTlc;
      tlcStart = tlcLimit;
    } while (currentTlc < fComponents.length);

    return fComponents[currentTlc].getCoreMetrics();
  }

  public float getCharAscent(int logicalIndex) {

    return getCoreMetricsAt(logicalIndex).ascent;
  }

  public float getCharDescent(int logicalIndex) {

    return getCoreMetricsAt(logicalIndex).descent;
  }

  public float getCharShift(int logicalIndex) {

    return getCoreMetricsAt(logicalIndex).ssOffset;
  }

  private float applyFunctionAtIndex(int logicalIndex, Function f) {

    if (logicalIndex < 0) {
      throw new IllegalArgumentException("Negative logicalIndex.");
    }

    int tlcStart = 0;

    for (int i = 0; i < fComponents.length; i++) {

      int tlcLimit = tlcStart + fComponents[i].getNumCharacters();
      if (tlcLimit > logicalIndex) {
        return f.computeFunction(this, i, logicalIndex - tlcStart);
      } else {
        tlcStart = tlcLimit;
      }
    }

    throw new IllegalArgumentException("logicalIndex too large.");
  }

  public float getCharAdvance(int logicalIndex) {

    return applyFunctionAtIndex(logicalIndex, fgAdvanceF);
  }

  public float getCharXPosition(int logicalIndex) {

    return applyFunctionAtIndex(logicalIndex, fgXPositionF);
  }

  public float getCharYPosition(int logicalIndex) {

    return applyFunctionAtIndex(logicalIndex, fgYPositionF);
  }

  public float getCharLinePosition(int logicalIndex) {

    return getCharXPosition(logicalIndex);
  }

  public float getCharLinePosition(int logicalIndex, boolean leading) {
    Function f = isCharLTR(logicalIndex) == leading ? fgXPositionF : fgPosAdvF;
    return applyFunctionAtIndex(logicalIndex, f);
  }

  public boolean caretAtOffsetIsValid(int offset) {

    if (offset < 0) {
      throw new IllegalArgumentException("Negative offset.");
    }

    int tlcStart = 0;

    for (int i = 0; i < fComponents.length; i++) {

      int tlcLimit = tlcStart + fComponents[i].getNumCharacters();
      if (tlcLimit > offset) {
        return fComponents[i].caretAtOffsetIsValid(offset - tlcStart);
      } else {
        tlcStart = tlcLimit;
      }
    }

    throw new IllegalArgumentException("logicalIndex too large.");
  }

  /**
   * map a component visual index to the logical index.
   */
  private int getComponentLogicalIndex(int vi) {
    if (fComponentVisualOrder == null) {
      return vi;
    }
    return fComponentVisualOrder[vi];
  }

  /**
   * map a component logical index to the visual index.
   */
  private int getComponentVisualIndex(int li) {
    if (fComponentVisualOrder == null) {
      return li;
    }
    for (int i = 0; i < fComponentVisualOrder.length; ++i) {
      if (fComponentVisualOrder[i] == li) {
        return i;
      }
    }
    throw new IndexOutOfBoundsException("bad component index: " + li);
  }

  public Rectangle2D getCharBounds(int logicalIndex) {

    if (logicalIndex < 0) {
      throw new IllegalArgumentException("Negative logicalIndex.");
    }

    int tlcStart = 0;

    for (int i = 0; i < fComponents.length; i++) {

      int tlcLimit = tlcStart + fComponents[i].getNumCharacters();
      if (tlcLimit > logicalIndex) {

        TextLineComponent tlc = fComponents[i];
        int indexInTlc = logicalIndex - tlcStart;
        Rectangle2D chBounds = tlc.getCharVisualBounds(indexInTlc);

        int vi = getComponentVisualIndex(i);
        chBounds.setRect(chBounds.getX() + locs[vi * 2],
            chBounds.getY() + locs[vi * 2 + 1],
            chBounds.getWidth(),
            chBounds.getHeight());
        return chBounds;
      } else {
        tlcStart = tlcLimit;
      }
    }

    throw new IllegalArgumentException("logicalIndex too large.");
  }

  private float getComponentShift(int index) {
    CoreMetrics cm = fComponents[index].getCoreMetrics();
    return cm.effectiveBaselineOffset(fBaselineOffsets);
  }

  public void draw(Graphics2D g2, float x, float y) {
    if (lp == null) {
      for (int i = 0, n = 0; i < fComponents.length; i++, n += 2) {
        TextLineComponent tlc = fComponents[getComponentLogicalIndex(i)];
        tlc.draw(g2, locs[n] + x, locs[n + 1] + y);
      }
    } else {
      AffineTransform oldTx = g2.getTransform();
      Point2D.Float pt = new Point2D.Float();
      for (int i = 0, n = 0; i < fComponents.length; i++, n += 2) {
        TextLineComponent tlc = fComponents[getComponentLogicalIndex(i)];
        lp.pathToPoint(locs[n], locs[n + 1], false, pt);
        pt.x += x;
        pt.y += y;
        AffineTransform at = tlc.getBaselineTransform();

        if (at != null) {
          g2.translate(pt.x - at.getTranslateX(), pt.y - at.getTranslateY());
          g2.transform(at);
          tlc.draw(g2, 0, 0);
          g2.setTransform(oldTx);
        } else {
          tlc.draw(g2, pt.x, pt.y);
        }
      }
    }
  }

  /**
   * Return the union of the visual bounds of all the components.
   * This incorporates the path.  It does not include logical
   * bounds (used by carets).
   */
  public Rectangle2D getVisualBounds() {
    Rectangle2D result = null;

    for (int i = 0, n = 0; i < fComponents.length; i++, n += 2) {
      TextLineComponent tlc = fComponents[getComponentLogicalIndex(i)];
      Rectangle2D r = tlc.getVisualBounds();

      Point2D.Float pt = new Point2D.Float(locs[n], locs[n + 1]);
      if (lp == null) {
        r.setRect(r.getMinX() + pt.x, r.getMinY() + pt.y,
            r.getWidth(), r.getHeight());
      } else {
        lp.pathToPoint(pt, false, pt);

        AffineTransform at = tlc.getBaselineTransform();
        if (at != null) {
          AffineTransform tx = AffineTransform.getTranslateInstance
              (pt.x - at.getTranslateX(), pt.y - at.getTranslateY());
          tx.concatenate(at);
          r = tx.createTransformedShape(r).getBounds2D();
        } else {
          r.setRect(r.getMinX() + pt.x, r.getMinY() + pt.y,
              r.getWidth(), r.getHeight());
        }
      }

      if (result == null) {
        result = r;
      } else {
        result.add(r);
      }
    }

    if (result == null) {
      result = new Rectangle2D.Float(Float.MAX_VALUE, Float.MAX_VALUE, Float.MIN_VALUE,
          Float.MIN_VALUE);
    }

    return result;
  }

  public Rectangle2D getItalicBounds() {

    float left = Float.MAX_VALUE, right = -Float.MAX_VALUE;
    float top = Float.MAX_VALUE, bottom = -Float.MAX_VALUE;

    for (int i = 0, n = 0; i < fComponents.length; i++, n += 2) {
      TextLineComponent tlc = fComponents[getComponentLogicalIndex(i)];

      Rectangle2D tlcBounds = tlc.getItalicBounds();
      float x = locs[n];
      float y = locs[n + 1];

      left = Math.min(left, x + (float) tlcBounds.getX());
      right = Math.max(right, x + (float) tlcBounds.getMaxX());

      top = Math.min(top, y + (float) tlcBounds.getY());
      bottom = Math.max(bottom, y + (float) tlcBounds.getMaxY());
    }

    return new Rectangle2D.Float(left, top, right - left, bottom - top);
  }

  public Shape getOutline(AffineTransform tx) {

    GeneralPath dstShape = new GeneralPath(GeneralPath.WIND_NON_ZERO);

    for (int i = 0, n = 0; i < fComponents.length; i++, n += 2) {
      TextLineComponent tlc = fComponents[getComponentLogicalIndex(i)];

      dstShape.append(tlc.getOutline(locs[n], locs[n + 1]), false);
    }

    if (tx != null) {
      dstShape.transform(tx);
    }
    return dstShape;
  }

  public int hashCode() {
    return (fComponents.length << 16) ^
        (fComponents[0].hashCode() << 3) ^ (fCharsLimit - fCharsStart);
  }

  public String toString() {
    StringBuilder buf = new StringBuilder();

    for (int i = 0; i < fComponents.length; i++) {
      buf.append(fComponents[i]);
    }

    return buf.toString();
  }

  /**
   * Create a TextLine from the text.  The Font must be able to
   * display all of the text.
   * attributes==null is equivalent to using an empty Map for
   * attributes
   */
  public static TextLine fastCreateTextLine(FontRenderContext frc,
      char[] chars,
      Font font,
      CoreMetrics lm,
      Map<? extends Attribute, ?> attributes) {

    boolean isDirectionLTR = true;
    byte[] levels = null;
    int[] charsLtoV = null;
    Bidi bidi = null;
    int characterCount = chars.length;

    boolean requiresBidi = false;
    byte[] embs = null;

    AttributeValues values = null;
    if (attributes != null) {
      values = AttributeValues.fromMap(attributes);
      if (values.getRunDirection() >= 0) {
        isDirectionLTR = values.getRunDirection() == 0;
        requiresBidi = !isDirectionLTR;
      }
      if (values.getBidiEmbedding() != 0) {
        requiresBidi = true;
        byte level = (byte) values.getBidiEmbedding();
        embs = new byte[characterCount];
        for (int i = 0; i < embs.length; ++i) {
          embs[i] = level;
        }
      }
    }

    // dlf: get baseRot from font for now???

    if (!requiresBidi) {
      requiresBidi = Bidi.requiresBidi(chars, 0, chars.length);
    }

    if (requiresBidi) {
      int bidiflags = values == null
          ? Bidi.DIRECTION_DEFAULT_LEFT_TO_RIGHT
          : values.getRunDirection();

      bidi = new Bidi(chars, 0, embs, 0, chars.length, bidiflags);
      if (!bidi.isLeftToRight()) {
        levels = BidiUtils.getLevels(bidi);
        int[] charsVtoL = BidiUtils.createVisualToLogicalMap(levels);
        charsLtoV = BidiUtils.createInverseMap(charsVtoL);
        isDirectionLTR = bidi.baseIsLeftToRight();
      }
    }

    Decoration decorator = Decoration.getDecoration(values);

    int layoutFlags = 0; // no extra info yet, bidi determines run and line direction
    TextLabelFactory factory = new TextLabelFactory(frc, chars, bidi, layoutFlags);

    TextLineComponent[] components = new TextLineComponent[1];

    components = createComponentsOnRun(0, chars.length,
        chars,
        charsLtoV, levels,
        factory, font, lm,
        frc,
        decorator,
        components,
        0);

    int numComponents = components.length;
    while (components[numComponents - 1] == null) {
      numComponents -= 1;
    }

    if (numComponents != components.length) {
      TextLineComponent[] temp = new TextLineComponent[numComponents];
      System.arraycopy(components, 0, temp, 0, numComponents);
      components = temp;
    }

    return new TextLine(frc, components, lm.baselineOffsets,
        chars, 0, chars.length, charsLtoV, levels, isDirectionLTR);
  }

  private static TextLineComponent[] expandArray(TextLineComponent[] orig) {

    TextLineComponent[] newComponents = new TextLineComponent[orig.length + 8];
    System.arraycopy(orig, 0, newComponents, 0, orig.length);

    return newComponents;
  }

  /**
   * Returns an array in logical order of the TextLineComponents on
   * the text in the given range, with the given attributes.
   */
  public static TextLineComponent[] createComponentsOnRun(int runStart,
      int runLimit,
      char[] chars,
      int[] charsLtoV,
      byte[] levels,
      TextLabelFactory factory,
      Font font,
      CoreMetrics cm,
      FontRenderContext frc,
      Decoration decorator,
      TextLineComponent[] components,
      int numComponents) {

    int pos = runStart;
    do {
      int chunkLimit = firstVisualChunk(charsLtoV, levels, pos, runLimit); // <= displayLimit

      do {
        int startPos = pos;
        int lmCount;

        if (cm == null) {
          LineMetrics lineMetrics = font.getLineMetrics(chars, startPos, chunkLimit, frc);
          cm = CoreMetrics.get(lineMetrics);
          lmCount = lineMetrics.getNumChars();
        } else {
          lmCount = (chunkLimit - startPos);
        }

        TextLineComponent nextComponent =
            factory.createExtended(font, cm, decorator, startPos, startPos + lmCount);

        ++numComponents;
        if (numComponents >= components.length) {
          components = expandArray(components);
        }

        components[numComponents - 1] = nextComponent;

        pos += lmCount;
      } while (pos < chunkLimit);

    } while (pos < runLimit);

    return components;
  }

  /**
   * Returns an array (in logical order) of the TextLineComponents representing
   * the text.  The components are both logically and visually contiguous.
   */
  public static TextLineComponent[] getComponents(StyledParagraph styledParagraph,
      char[] chars,
      int textStart,
      int textLimit,
      int[] charsLtoV,
      byte[] levels,
      TextLabelFactory factory) {

    FontRenderContext frc = factory.getFontRenderContext();

    int numComponents = 0;
    TextLineComponent[] tempComponents = new TextLineComponent[1];

    int pos = textStart;
    do {
      int runLimit = Math.min(styledParagraph.getRunLimit(pos), textLimit);

      Decoration decorator = styledParagraph.getDecorationAt(pos);

      Object graphicOrFont = styledParagraph.getFontOrGraphicAt(pos);

      if (graphicOrFont instanceof GraphicAttribute) {
        // AffineTransform baseRot = styledParagraph.getBaselineRotationAt(pos);
        // !!! For now, let's assign runs of text with both fonts and graphic attributes
        // a null rotation (e.g. the baseline rotation goes away when a graphic
        // is applied.
        AffineTransform baseRot = null;
        GraphicAttribute graphicAttribute = (GraphicAttribute) graphicOrFont;
        do {
          int chunkLimit = firstVisualChunk(charsLtoV, levels,
              pos, runLimit);

          GraphicComponent nextGraphic =
              new GraphicComponent(graphicAttribute, decorator, charsLtoV, levels, pos, chunkLimit,
                  baseRot);
          pos = chunkLimit;

          ++numComponents;
          if (numComponents >= tempComponents.length) {
            tempComponents = expandArray(tempComponents);
          }

          tempComponents[numComponents - 1] = nextGraphic;

        } while (pos < runLimit);
      } else {
        Font font = (Font) graphicOrFont;

        tempComponents = createComponentsOnRun(pos, runLimit,
            chars,
            charsLtoV, levels,
            factory, font, null,
            frc,
            decorator,
            tempComponents,
            numComponents);
        pos = runLimit;
        numComponents = tempComponents.length;
        while (tempComponents[numComponents - 1] == null) {
          numComponents -= 1;
        }
      }

    } while (pos < textLimit);

    TextLineComponent[] components;
    if (tempComponents.length == numComponents) {
      components = tempComponents;
    } else {
      components = new TextLineComponent[numComponents];
      System.arraycopy(tempComponents, 0, components, 0, numComponents);
    }

    return components;
  }

  /**
   * Create a TextLine from the Font and character data over the
   * range.  The range is relative to both the StyledParagraph and the
   * character array.
   */
  public static TextLine createLineFromText(char[] chars,
      StyledParagraph styledParagraph,
      TextLabelFactory factory,
      boolean isDirectionLTR,
      float[] baselineOffsets) {

    factory.setLineContext(0, chars.length);

    Bidi lineBidi = factory.getLineBidi();
    int[] charsLtoV = null;
    byte[] levels = null;

    if (lineBidi != null) {
      levels = BidiUtils.getLevels(lineBidi);
      int[] charsVtoL = BidiUtils.createVisualToLogicalMap(levels);
      charsLtoV = BidiUtils.createInverseMap(charsVtoL);
    }

    TextLineComponent[] components =
        getComponents(styledParagraph, chars, 0, chars.length, charsLtoV, levels, factory);

    return new TextLine(factory.getFontRenderContext(), components, baselineOffsets,
        chars, 0, chars.length, charsLtoV, levels, isDirectionLTR);
  }

  /**
   * Compute the components order from the given components array and
   * logical-to-visual character mapping.  May return null if canonical.
   */
  private static int[] computeComponentOrder(TextLineComponent[] components,
      int[] charsLtoV) {

        /*
         * Create a visual ordering for the glyph sets.  The important thing
         * here is that the values have the proper rank with respect to
         * each other, not the exact values.  For example, the first glyph
         * set that appears visually should have the lowest value.  The last
         * should have the highest value.  The values are then normalized
         * to map 1-1 with positions in glyphs.
         *
         */
    int[] componentOrder = null;
    if (charsLtoV != null && components.length > 1) {
      componentOrder = new int[components.length];
      int gStart = 0;
      for (int i = 0; i < components.length; i++) {
        componentOrder[i] = charsLtoV[gStart];
        gStart += components[i].getNumCharacters();
      }

      componentOrder = BidiUtils.createContiguousOrder(componentOrder);
      componentOrder = BidiUtils.createInverseMap(componentOrder);
    }
    return componentOrder;
  }


  /**
   * Create a TextLine from the text.  chars is just the text in the iterator.
   */
  public static TextLine standardCreateTextLine(FontRenderContext frc,
      AttributedCharacterIterator text,
      char[] chars,
      float[] baselineOffsets) {

    StyledParagraph styledParagraph = new StyledParagraph(text, chars);
    Bidi bidi = new Bidi(text);
    if (bidi.isLeftToRight()) {
      bidi = null;
    }
    int layoutFlags = 0; // no extra info yet, bidi determines run and line direction
    TextLabelFactory factory = new TextLabelFactory(frc, chars, bidi, layoutFlags);

    boolean isDirectionLTR = true;
    if (bidi != null) {
      isDirectionLTR = bidi.baseIsLeftToRight();
    }
    return createLineFromText(chars, styledParagraph, factory, isDirectionLTR, baselineOffsets);
  }



    /*
     * A utility to get a range of text that is both logically and visually
     * contiguous.
     * If the entire range is ok, return limit, otherwise return the first
     * directional change after start.  We could do better than this, but
     * it doesn't seem worth it at the moment.
    private static int firstVisualChunk(int order[], byte direction[],
                                        int start, int limit)
    {
        if (order != null) {
            int min = order[start];
            int max = order[start];
            int count = limit - start;
            for (int i = start + 1; i < limit; i++) {
                min = Math.min(min, order[i]);
                max = Math.max(max, order[i]);
                if (max - min >= count) {
                    if (direction != null) {
                        byte baseLevel = direction[start];
                        for (int j = start + 1; j < i; j++) {
                            if (direction[j] != baseLevel) {
                                return j;
                            }
                        }
                    }
                    return i;
                }
            }
        }
        return limit;
    }
     */

  /**
   * When this returns, the ACI's current position will be at the start of the
   * first run which does NOT contain a GraphicAttribute.  If no such run exists
   * the ACI's position will be at the end, and this method will return false.
   */
  static boolean advanceToFirstFont(AttributedCharacterIterator aci) {

    for (char ch = aci.first();
        ch != CharacterIterator.DONE;
        ch = aci.setIndex(aci.getRunLimit())) {

      if (aci.getAttribute(TextAttribute.CHAR_REPLACEMENT) == null) {
        return true;
      }
    }

    return false;
  }

  static float[] getNormalizedOffsets(float[] baselineOffsets, byte baseline) {

    if (baselineOffsets[baseline] != 0) {
      float base = baselineOffsets[baseline];
      float[] temp = new float[baselineOffsets.length];
      for (int i = 0; i < temp.length; i++) {
        temp[i] = baselineOffsets[i] - base;
      }
      baselineOffsets = temp;
    }
    return baselineOffsets;
  }

  static Font getFontAtCurrentPos(AttributedCharacterIterator aci) {

    Object value = aci.getAttribute(TextAttribute.FONT);
    if (value != null) {
      return (Font) value;
    }
    if (aci.getAttribute(TextAttribute.FAMILY) != null) {
      return Font.getFont(aci.getAttributes());
    }

    int ch = CodePointIterator.create(aci).next();
    if (ch != CodePointIterator.DONE) {
      FontResolver resolver = FontResolver.getInstance();
      return resolver.getFont(resolver.getFontIndex(ch), aci.getAttributes());
    }
    return null;
  }

  /*
   * The new version requires that chunks be at the same level.
   */
  private static int firstVisualChunk(int order[], byte direction[],
      int start, int limit) {
    if (order != null && direction != null) {
      byte dir = direction[start];
      while (++start < limit && direction[start] == dir) {
      }
      return start;
    }
    return limit;
  }

  /*
   * create a new line with characters between charStart and charLimit
   * justified using the provided width and ratio.
   */
  public TextLine getJustifiedLine(float justificationWidth, float justifyRatio, int justStart,
      int justLimit) {

    TextLineComponent[] newComponents = new TextLineComponent[fComponents.length];
    System.arraycopy(fComponents, 0, newComponents, 0, fComponents.length);

    float leftHang = 0;
    float adv = 0;
    float justifyDelta = 0;
    boolean rejustify = false;
    do {
      adv = getAdvanceBetween(newComponents, 0, characterCount());

      // all characters outside the justification range must be in the base direction
      // of the layout, otherwise justification makes no sense.

      float justifyAdvance = getAdvanceBetween(newComponents, justStart, justLimit);

      // get the actual justification delta
      justifyDelta = (justificationWidth - justifyAdvance) * justifyRatio;

      // generate an array of GlyphJustificationInfo records to pass to
      // the justifier.  Array is visually ordered.

      // get positions that each component will be using
      int[] infoPositions = new int[newComponents.length];
      int infoCount = 0;
      for (int visIndex = 0; visIndex < newComponents.length; visIndex++) {
        int logIndex = getComponentLogicalIndex(visIndex);
        infoPositions[logIndex] = infoCount;
        infoCount += newComponents[logIndex].getNumJustificationInfos();
      }
      GlyphJustificationInfo[] infos = new GlyphJustificationInfo[infoCount];

      // get justification infos
      int compStart = 0;
      for (int i = 0; i < newComponents.length; i++) {
        TextLineComponent comp = newComponents[i];
        int compLength = comp.getNumCharacters();
        int compLimit = compStart + compLength;
        if (compLimit > justStart) {
          int rangeMin = Math.max(0, justStart - compStart);
          int rangeMax = Math.min(compLength, justLimit - compStart);
          comp.getJustificationInfos(infos, infoPositions[i], rangeMin, rangeMax);

          if (compLimit >= justLimit) {
            break;
          }
        }
      }

      // records are visually ordered, and contiguous, so start and end are
      // simply the places where we didn't fetch records
      int infoStart = 0;
      int infoLimit = infoCount;
      while (infoStart < infoLimit && infos[infoStart] == null) {
        ++infoStart;
      }

      while (infoLimit > infoStart && infos[infoLimit - 1] == null) {
        --infoLimit;
      }

      // invoke justifier on the records
      TextJustifier justifier = new TextJustifier(infos, infoStart, infoLimit);

      float[] deltas = justifier.justify(justifyDelta);

      boolean canRejustify = rejustify == false;
      boolean wantRejustify = false;
      boolean[] flags = new boolean[1];

      // apply justification deltas
      compStart = 0;
      for (int i = 0; i < newComponents.length; i++) {
        TextLineComponent comp = newComponents[i];
        int compLength = comp.getNumCharacters();
        int compLimit = compStart + compLength;
        if (compLimit > justStart) {
          int rangeMin = Math.max(0, justStart - compStart);
          int rangeMax = Math.min(compLength, justLimit - compStart);
          newComponents[i] = comp.applyJustificationDeltas(deltas, infoPositions[i] * 2, flags);

          wantRejustify |= flags[0];

          if (compLimit >= justLimit) {
            break;
          }
        }
      }

      rejustify = wantRejustify && !rejustify; // only make two passes
    } while (rejustify);

    return new TextLine(frc, newComponents, fBaselineOffsets, fChars, fCharsStart,
        fCharsLimit, fCharLogicalOrder, fCharLevels,
        fIsDirectionLTR);
  }

  // return the sum of the advances of text between the logical start and limit
  public static float getAdvanceBetween(TextLineComponent[] components, int start, int limit) {
    float advance = 0;

    int tlcStart = 0;
    for (int i = 0; i < components.length; i++) {
      TextLineComponent comp = components[i];

      int tlcLength = comp.getNumCharacters();
      int tlcLimit = tlcStart + tlcLength;
      if (tlcLimit > start) {
        int measureStart = Math.max(0, start - tlcStart);
        int measureLimit = Math.min(tlcLength, limit - tlcStart);
        advance += comp.getAdvanceBetween(measureStart, measureLimit);
        if (tlcLimit >= limit) {
          break;
        }
      }

      tlcStart = tlcLimit;
    }

    return advance;
  }

  LayoutPathImpl getLayoutPath() {
    return lp;
  }
}
